This invention relates to a system and method for recognizing user specified pen-based gestures. More particularly, the method utilizes Hidden Markov Models (HMMs) that are applied to an incremental training procedure and a recognition procedure that incorporates a fast pruning approach.
While the invention is particularly directed to the art of gesture recognition and training therefor, and thus will be described with specific reference thereto, it will be appreciated that the invention may have applicability to other areas, such as speech recognition and word matching for pen-based systems.
By way of background, an active and rapidly growing area of personal computing today, both in the academic and commercial arenas, involves computers using pen-based user interfaces. Examples of such devices incorporating pen-based user interfaces include Personal Digital Assistants (PDAs) which are useful for maintaining personal information such as notes, calenders, etc. Recognition of pen gestures--which form the basis of command and data input--is a very important factor in the success of PDAs and other pen-based systems.
More specifically, single stroke gestures provide an intuitive user interface and are useful for editing text and graphics in much the same way as a teacher would use special correlation characters when grading students' homework. Furthermore, use of recognizable gestures is necessary for devices which lack keyboards and rely entirely on pen-based input.
Presently, there are a number of applications in which gestures form a part of the user interface. However, there are numerous problems with creating a reliable recognition scheme. The main problem is the large variety of gesture types and wide variability in the manners in which different users may draw the ago same gesture.
The variety of gestures presents a problem in selecting the characteristic which best distinguishes between gestures. For instance, that which distinguishes a square from a circle is the corners. However, this is not a valid distinction if one desires to distinguish a square from a rectangle. Accordingly, it is difficult to choose a distinguishing feature even if the gestures to be recognized are known, let alone if the gesture is not known in advance.
On the other hand, choosing characteristics that are too particular also limits the range of gestures that can be successfully distinguished. For instance, if a feature set for a square includes four corners and specific dimensional data, then only squares satisfying that criteria will be recognized, not all squares.
Known gesture recognizers require improvements. First, in some cases, the accuracy of these gesture recognizers is not acceptable for use in real world applications. When too many errors are made during gesture recognition, the user will usually revert to clumsier but more accurate input devices such as the keyboard or pull down menus.
Second, the recognizers that are known are specifically designed around a fixed set of gestures--the application is restricted to gestures in this predefined set. In some applications, this is an undesirable restriction. In addition, the user must often draw the gestures in the way prescribed by the system in order for them to be correctly recognized.
Third, in traditional approaches to recognition, a gesture is run through, or processed by, a recognizer and a likelihood that the subject gesture belongs to each of a variety of classes in the recognizer is determined, and nothing else. Accordingly, the class having the best likelihood is determined but that class is not necessarily the correct class. It is only the class with the best likelihood. Thus, the results are unreliable and not reached efficiently.
It would, therefore, be desirable to include in the process a normalization (or a ground level or threshold) to determine that the best class is, at the very least, above a certain level. This feature is not present in known gesture recognition systems.
The present invention contemplates a new and improved gesture recognition method which resolves the shortcomings of the prior schemes.